// https://leetcode.cn/problems/coin-change-ii/

// 算法思路总结：
// 1. 动态规划解决零钱兑换II问题（组合数）
// 2. 状态定义：dp[i][j]表示前i种硬币凑出金额j的组合数
// 3. 状态转移：不选当前硬币 + 选当前硬币（完全背包）
// 4. 关键点：内层循环正序，允许硬币重复使用
// 5. 初始化：dp[0][0]=1（金额0有1种方案）
// 6. 时间复杂度：O(n×amount)，空间复杂度：O(n×amount)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int change(int amount, vector<int>& coins) 
    {
        int m = coins.size();
        vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(amount + 1, 0));
        dp[0][0] = 1u;

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 0 ; j <= amount ; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i - 1] >= 0)
                {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                } 
            }
        }

        return dp[m][amount];
    }
};

int main()
{
    vector<int> coins1 = {1, 2, 5}, coins2 = {2};
    int amount1 = 5, amount2 = 3;

    Solution sol;

    cout << sol.change(amount1, coins1) << endl;
    cout << sol.change(amount2, coins2) << endl;

    return 0;
}